Flatten Nested List Iterator
Leetcode #341 | Medium | Рекурсия | Design
Идея
Заводим обычный лист и индекс. При next увеливаем индекс, перед этим отдав элемент. hasNext обычное сравнение index и list.size(). На старте вложенность убираем рекурсией. Внимательно надо изучить методы апишки.
Big-O
- Время
O(N) - Память
O(N)
Код
public class NestedIterator implements Iterator<Integer> {
private List<Integer> list = new ArrayList<>();
private int idx = 0;
public NestedIterator(List<NestedInteger> nestedList) { dfs(nestedList); }
private void dfs(List<NestedInteger> nested) {
for (NestedInteger el : nested) {
if (el.isInteger()) list.add(el.getInteger());
else dfs(el.getList());
}
}
public Integer next() { return list.get(idx++); }
public boolean hasNext() { return idx < list.size(); }
}